#include <iostream>
using namespace std;

// 请模拟实现红黑树的插入--注意：为了后序封装map和set，本文在实现时给红黑树多增加了一个头结点

enum Color {
	RED,BLACK
};

template<class T>
struct RBTreeNode {
	RBTreeNode(const T& data = T(), Color color = RED)
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _color(color)
	{}

	RBTreeNode<T>* _pLeft;
	RBTreeNode<T>* _pRight;
	RBTreeNode<T>* _pParent;
	T _data;
	Color _color;
};



template<class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	RBTree()
	{
		_pHead = new Node;
		_pHead->_pLeft = _pHead;
		_pHead->_pRight = _pHead;
	}

	// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
	// 注意：为了简单起见，本次实现红黑树不存储重复性元素
	bool Insert(const T& data)
	{
		Node*& pRoot = GetRoot();
		if (pRoot == nullptr) { //根节点为空时
			pRoot = new Node(data, BLACK); //相当于开辟一个空间，然后赋值为黑色
			pRoot->_pParent = _pHead;
			return true;
		}
		
		Node* pCur = pRoot, *pParent = nullptr;
		while (pCur) {
			pParent = pCur;
			if (data < pCur->_data) pCur = pCur->_pLeft;
			else if (data > pCur->_data) pCur = pCur->_pRight;
			else return false;
		}

		pCur = new Node(data);
		pCur->_color = RED;
		if (data < pParent->_data) pParent->_pLeft = pCur;
		else pParent->_pRight = pCur;
		pCur->_pParent = pParent;
	
		// pCur新节点默认颜色：红色
		// 如果pParent的颜色是黑色的，满足红黑树性质
		// 如果pParent的颜色是红色的，违反了性质三--不能有连在一起的红色节点

		while (pParent != _pHead && pParent->_color == RED)
		{
			Node* grandFather = pParent->_pParent;
			if (pParent == grandFather->_pLeft) {
				Node* uncle = grandFather->_pRight;

				if (uncle && uncle->_color == RED)
				{
					pParent->_color = uncle->_color = BLACK;
					grandFather->_color = RED;
					
					pCur = grandFather;
					pParent = pCur->_pParent;
				}
				else
				{
					if (pParent->_pRight == pCur)
					{
						RotateL(pParent);
						swap(pCur, pParent);
					}

					pParent->_color == BLACK;
					grandFather->_color = RED;
					RotateR(grandFather);
				}
			}
			else
			{
				Node* uncle = grandFather->_pLeft;

				if (uncle && uncle->_color == RED)
				{
					pParent->_color = uncle->_color = BLACK;
					grandFather->_color = RED;
					
					pCur = grandFather;
					pParent = pCur->_pParent;
				}
				else
				{
					if (pParent->_pLeft == pCur)
					{
						RotateR(pParent);
						swap(pCur, pParent);
					}

					pParent->_color = BLACK;
					grandFather->_color = RED;
					RotateL(grandFather);
				}
			}
		}
		pRoot->_color = BLACK;
		_pHead->_pLeft = LeftMost();
		_pHead->_pRight = RightMost();

		return true;
	}

	// 检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptr
	Node* Find(const T& data)
	{
		Node* cur = GetRoot();
		while (cur)
		{
			if (cur->_data < data) cur = cur->_pRight;
			else if (cur->_data > data) cur = cur->_pLeft;
			else  return cur;
		}
		return nullptr;
	}

	// 为了操作树简单起见：获取根节点
	Node*& GetRoot()
	{
		return _pHead->_pParent; //虚拟头节点的父亲为根节点
	}

	void InOrder()
	{
		_InOrder(GetRoot());
	}

	// 获取红黑树最左侧节点
	Node* LeftMost()
	{
		Node* pRoot = GetRoot(); //先获取根节点
		if (pRoot == nullptr) return _pHead;

		Node* pCur = pRoot;
		while (pCur->_pLeft) pCur = pCur->_pLeft;
		
		return pCur;
	}

	// 获取红黑树最右侧节点
	Node* RightMost()
	{
		Node* pRoot = GetRoot();
		if (pRoot == nullptr) return _pHead;

		Node* pCur = pRoot;
		while (pCur->_pRight) pCur = pCur->_pRight;
		
		return pCur;
	}

	// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
	bool IsValidRBTRee()
	{
		Node* pRoot = GetRoot();
		if (pRoot == nullptr) {
			cout << "该树为空" << endl;
			return true;
		}
		if (pRoot->_color != BLACK) {
			cout << "违法性质一：根节点需要为黑色" << endl;
			return false;
		}

		// 获取任意一条路径上黑色节点的个数
		size_t blackCount = 0;
		Node* pCur = pRoot;
		while (pCur) {
			if (pCur->_color == BLACK) blackCount++;
			pCur = pCur->_pLeft;
		}
		size_t pathBlack = 0;

		return _IsValidRBTRee(pRoot, blackCount, pathBlack);
	}
private:
	
	bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack)
	{
		if (pRoot == nullptr) return true;
		if (pRoot->_color == BLACK) pathBlack ++ ;
		Node* pParent = pRoot->_pParent;
		if (pParent != _pHead &&
			RED == pParent->_color && RED == pRoot->_color)
		{
			cout << "违反性质3：不能存在连在一起的红色节点" << endl;
			return false;
		}

		// 叶子节点
		if (nullptr == pRoot->_pLeft && nullptr == pRoot->_pRight)
		{
			if (pathBlack != blackCount)
			{
				cout << "违反性质4：每条路径中黑色节点个数均相同" << endl;
				return false;
			}
		}

		return _IsValidRBTRee(pRoot->_pLeft, blackCount, pathBlack) &&
			_IsValidRBTRee(pRoot->_pRight, blackCount, pathBlack);
	}
	
	// 左单旋
	void RotateL(Node* pParent)
	{

		Node* pSubR = pParent->_pRight, * pSubRL = pSubR->_pLeft;
		Node* pPParent = pParent->_pParent;

		pParent->_pRight = pSubRL;
		if (pSubRL) pSubRL->_pParent = pParent;

		pSubR->_pLeft = pParent;
		pParent->_pParent = pSubR;
		pSubR->_pParent = pPParent;

		if (pPParent == _pHead) {
			_pHead->_pParent = pSubR;
		}
		else {
			if (pPParent->_pLeft == pParent) pPParent->_pLeft = pSubR;
			else pPParent->_pRight = pSubR;
		}
	}

	// 右单旋
	void RotateR(Node* pParent)
	{
		Node* pRoot = GetRoot();

		Node* pSubL = pParent->_pLeft, * pSubLR = pSubL->_pRight;
		Node* pPParent = pParent->_pParent;

		pParent->_pLeft = pSubLR;
		if (pSubLR) pSubLR->_pParent = pParent;


		pSubL->_pRight = pParent;
		pParent->_pParent = pSubL;
		pSubL->_pParent = pPParent;

		if (pPParent == _pHead) {
			_pHead->_pParent = pSubL;
		}
		else {
			if (pPParent->_pLeft == pParent) pPParent->_pLeft = pSubL;
			else pPParent->_pRight = pSubL;
		}
	}

	void _InOrder(Node* pRoot)
	{
		if (pRoot)
		{
			_InOrder(pRoot->_pLeft);
			cout << pRoot->_data << " ";
			_InOrder(pRoot->_pRight);
		}
	}

	

private:
	Node* _pHead;
};



int main()
{
	RBTree<int> t;
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	
	t.InOrder();
	cout<<endl;
	cout << t.IsValidRBTRee() << endl;
}